#include <bits/stdc++.h>
using namespace std;

int trap(vector<int>& height) {
    stack<int> s;
    int l = height.size();
    int ans = 0;
    for(int i = 0; i < l; ++i) {
        while(!s.empty() && height[s.top()] < height[i]){
            int top = s.top();
            s.pop();
            if(s.empty()) {
                break;
            }
            int left = s.top();
            int width = i-left-1;
            int hight = min(height[left], height[i]) - height[top];
            ans += width * hight;
        }
        s.push(i);
    }
    return ans;   
}